package com.mid;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by Lxk on 2020/2/1.
 */
public class Solution93 {

    private Stack<String> stack = new Stack<>();

    private List<String> res = new ArrayList<>();

    private void findSuitIp(int pos, int limit, int end, String s) {
        if (stack.size() >= limit || pos >= end) {
            if (stack.size() == limit && pos == end) {
                StringBuffer sb = new StringBuffer();
                for (String val : stack) {
                    sb.append(val);
                    sb.append(".");
                }
                res.add(sb.substring(0, sb.toString().length() - 1));
            }
            return;
        }
        for (int i = 1; i <= 3; i++) {
            String curStr = s.substring(pos, pos + i > end ? end : pos + i);
            if (curStr != null && curStr.length() > 1 && curStr.charAt(0) == '0') {
                continue;
            }
            if (Integer.valueOf(curStr) >= 0 && Integer.valueOf(curStr) <= 255) {
                stack.push(curStr);
                findSuitIp(pos + i, limit, end, s);
                stack.pop();
            }
        }
    }

    public List<String> restoreIpAddresses(String s) {
        findSuitIp(0, 4, s.length(), s);
        return res;
    }

    public static void main(String[] args) {
        String input = new String("25525511135");
        Solution93 solution93 = new Solution93();
        System.out.println(solution93.restoreIpAddresses(input));
    }

}
